#include <iostream>
#include <cstdio>
#include <stack>
#include <algorithm>
#include <vector>
#include <string>
#include <cstring>

using namespace std;

class Solution {
    vector<vector<int> > fgs;
    vector<int> X={1,-1,0,0};
    vector<int> Y={0,0,1,-1};
public:
    bool dfs(char* matrix, int rows, int cols, char* str,int cur,int ind,int jnd){
        if(ind<0||ind>=rows||jnd<0||jnd>=cols||fgs[ind][jnd] ||matrix[ind*cols+jnd]!=str[cur]){
            return false;
        }
        // cout << ind << " " << jnd <<endl;
        fgs[ind][jnd]=1;
        if(cur==strlen(str)-1){
            return true;
        }else{
            for(int i=0;i<4;i++){
                int new_i=ind+X[i];
                int new_j=jnd+Y[i];
                
                // cout <<"ind: " << ind<<" jnd: "<<jnd<< " new_i: "<< new_i<< " new_j: " << new_j << " cur:  "<< cur<<endl;
                bool ans=dfs(matrix,rows,cols,str,cur+1,new_i,new_j);
                if(ans) return ans;
            }
            fgs[ind][jnd]=0;
        }
        return false;
    }

    bool hasPath(char* matrix, int rows, int cols, char* str)
    {
       for(int i=0;i<rows;i++){
            for(int j=0;j<cols;j++){
                if(matrix[i*cols+j]==str[0]){
                    fgs=vector<vector<int> >(rows,vector<int>(cols,0));
                    if(dfs(matrix,rows,cols,str,0,i,j)) return true;
                }
            }
        }
        return false;
    }
};

int main(){
    char mt[][4]{{'a','b','c','e'},{'s','f','c','s'},{'a','d','e','e'}};
    char m[]{'b','c','c','e','s','\0'};
    Solution s;
    bool ans=s.hasPath((char *)&mt,3,4,(char *)&m);
    cout << "ans= "<< ans<<endl;
    // char *cc=(char *)&mt;
    // cout << cc[1*4+2]<<endl;
    

    return 0;
}